---
id: 5900f4da1000cf542c50ffed
title: 'Завдання 366: гра в камені III'
challengeType: 1
forumTopicId: 302027
dashedName: problem-366-stone-game-iii
---

# --description--

В гру грають двоє гравців, Антон та Бернгард.

Вони використовують купку з $n$ каменів.

Перший гравець може взяти будь-яку додатну кількість каменів, але не всю купу.

Потім кожен гравець може забрати щонайбільше вдвічі більше каменів ніж його суперник в попередньому ході.

Виграє той, хто забрав останній камінь.

Наприклад, $n = 5$

Якщо перший гравець бере більше одного каменя, наступний гравець зможе забрати все, що залишиться.

Якщо перший гравець бере один камінь, залишаючи чотири, то його суперник також візьме один камінь, залишивши три.

Перший гравець не може забрати всі три, адже він може взяти не більше $2 \times 1 = 2$ каменів. Скажімо, він також бере один камінь, залишаючи 2.

Другий гравець може забрати два камені, які залишились, та переможе.

Тому 5 є програшною позицією для першого гравця.

Для деяких виграшних позицій існує більше одного можливого ходу для першого гравця.

Наприклад, якщо $n = 17$, то перший гравець може взяти один або чотири камені.

Нехай $M(n)$ буде максимальною кількістю каменів, які може взяти перший гравець для виграшної позиції за перший хід. Тоді $M(n) = 0$ для будь-якої іншої позиції.

$\sum M(n)$ за умови $n ≤ 100$ дорівнює 728.

Знайдіть $\sum M(n)$ за умови $n ≤ {10}^{18}$. Надайте відповідь за модулем ${10}^8$.

# --hints--

`stoneGameThree()` має повернути `88351299`.

```js
assert.strictEqual(stoneGameThree(), 88351299);
```

# --seed--

## --seed-contents--

```js
function stoneGameThree() {

  return true;
}

stoneGameThree();
```

# --solutions--

```js
// solution required
```
